/**
 * @param {string} s
 * @return {string}
 */
export var longestPrefix = function (s) {
  let i = 0,
    j = s.length - 1
  let ans = ''
  let prefix = ''
  let suffix = ''
  while (i < s.length - 1 && j > 0) {
    prefix = prefix + s[i]
    suffix = s[j] + suffix
    if (prefix === suffix) ans = prefix
    i++
    j--
  }
  return ans
}

/**
 kmp算法 （next数组）
 此法更快
 * @param {string} s
 * @return {string}
 */
export var longestPrefix2 = function (s) {
  let j = 0,
    next = [0]
  for (let i = 1; i < s.length; i++) {
    while (j > 0 && s[j] !== s[i]) j = next[j - 1]
    if (s[j] === s[i]) {
      j++
    }
    next.push(j)
  }
  return s.substring(0, next[s.length - 1])
}
